Packet switching networks such as those using self-routing switching nodes communicate packets on the basis of address information contained within the packets. In such self-routing networks, there is generally only one unique route between each input and output pair of the network. This characteristic makes fault diagnosis easy since a faulty switching node within the network can be located by the intersection of two paths which share only that node. A problem with the existence of only one unique route is that it reduces reliability and the ability to operate under unbalanced traffic conditions. Reliability is a problem since the failure of a single node or link between nodes causes many routes to be unavailable. The traffic problem arises because a particular traffic pattern may cause a number of routes communicating a large amount of traffic to be channeled through one node. When this occurs, the traffic capacity on these paths is limited to that of a single node.
One method for overcoming the potential reliability and traffic problems of a self-routing packet switching network is disclosed in the above-identified application of J. S. Turner, Ser. No. 438,572. That application describes a fast packet system in which packet switching networks are interconnected by trunks with each trunk terminated on both ends by a trunk controller. Each of the switching networks comprises duplicated switching arrays. During nonfailure conditions, the duplicated network arrays are both normally operational, and any given trunk controller cooperates with the duplicate network arrays to distribute the workload of packet switching by rotating or alternating the routing of packets between each of the arrays and the trunk attached to that trunk controller. In the event that one switching array fails, the failure is automatically detected by the trunk controller which then routes packets only to the nonfailing switching array. This technique is more expensive than a single unduplicated array due to the additional cost of duplicating the switching array. In addition, an unbalance of traffic load is only reduced by half since there are only two paths (one path through each switching array) available for routing packets.
One known method for alleviating the reliability and traffic problems in a self-routing network is discussed in the report entitled, "Development of a Voice Funnel System", Bolt, Beranek and Newman, Inc., Report No. 4098, August, 1979, pp.III-29 through 76, which discloses the use of an extra stage of banyan switching nodes at the input of a self-routing network to resolve the previously mentioned problems. The report proposes that this extra stage of switching be identical to other stages of the network and be utilized by adding an extra bit of addressing to the address field of each packet being routed through the switching network. The extra address bit would be controlled by hardware or software external to the switching network and would determine the route through the switching network. The hardware or software would use this bit so as to avoid a node which was failing or experiencing heavy traffic. Whereas the method proposed by the report allows the addition of more than one unique route through the switching network, it requires that the decision of which route to use be made external to the packet switching network.